#include<iostream>
#include<string>
#include<stack>
#include<list>
#include<cmath>

using namespace std;
class Combination;
class TreeNode
{
private:
    /* data */
    
public:
    TreeNode * leftChild;
    TreeNode * rightChild;
    int value;
    TreeNode(int tempvalue):value(tempvalue),leftChild(NULL),rightChild(NULL)
    {}
    //~TreeNode();
};


class BinaryTree
{
public:
    /* data */
    TreeNode * root;
    stack<TreeNode *> * stackForDelete;
    BinaryTree(/* args */);
    ~BinaryTree();
    void CreateBiTreeInMid(TreeNode* &ptemp,string presequence,string insequence); //实现由先序、中序序列构造二叉树的算法
    void CreateBiTreePostIN(TreeNode* &,string,string);
    void MidSearchBiTree(TreeNode*);
    int TreeNode1Sum(TreeNode*);
    int TreeNode2Sum(TreeNode*);
    int TreeNode0Sum(TreeNode*);
    list<Combination*> * PostSearchBiTree();
    int GetTheHeight();
    int GetTheWidth();
    void SwapTheBinaryTree(TreeNode * ptemp);
    bool JudgeComplete();

};

BinaryTree::BinaryTree(/* args */)
{
    root = NULL;
    stackForDelete = new stack<TreeNode*>;
}

BinaryTree::~BinaryTree()
{
    TreeNode* ptemp;
    while(!stackForDelete->empty())
    {
        
        ptemp = stackForDelete->top();
        stackForDelete->pop();
        delete ptemp;
        cout<<"STACKFORDELETE:"<<stackForDelete->size()<<endl;
    }
    
    delete stackForDelete;
}

void BinaryTree::CreateBiTreeInMid(TreeNode * &ptemp,string presequence,string insequence)
{
    /* 1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。
若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。 */
    if(presequence.length()==0)
    {
        ptemp = NULL;
        return;
    }
    char rootNode = presequence[0];  //将根节点从先序字符串中提取出来
    int index = insequence.find(rootNode);
    string lchild_insequence = insequence.substr(0,index);
    string rchild_insequence = insequence.substr(index+1);
    int lchild_length = lchild_insequence.length();
    int rchild_length = rchild_insequence.length();
    string lchild_presequence = presequence.substr(1,lchild_length);
    string rchild_presequence = presequence.substr(1+lchild_length);
    int tempvalue = rootNode - '0';
    
    ptemp = new TreeNode(tempvalue);
    stackForDelete->push(ptemp);
    cout<<"ptemp->value:"<<ptemp->value<<endl;
    
    
    CreateBiTreeInMid(ptemp->leftChild,lchild_presequence,lchild_insequence);
    CreateBiTreeInMid(ptemp->rightChild,rchild_presequence,rchild_insequence);

}

void BinaryTree::CreateBiTreePostIN(TreeNode * & ptemp,string postsequence,string midsequence)
{
    if(postsequence.length()==0)
    {
        ptemp = NULL;
        return;
    }
    char rootNode = postsequence[postsequence.length()-1];
    int index = midsequence.find(rootNode);
    string lchild_midsequence = midsequence.substr(0,index);
    string rchild_midsequence = midsequence.substr(index+1);
    int lchild_length = lchild_midsequence.length();
    int rchild_length = rchild_midsequence.length();
    string lchild_postsequence = postsequence.substr(0,index);
    cout<<"lchild_postsequence:"<<lchild_postsequence<<endl;
    string rchild_postsequence = postsequence.substr(index,postsequence.length()-index-1);
    cout<<"rchild_postsequence:"<<rchild_postsequence<<endl;
    int tempvalue = rootNode-'0';
    ptemp = new TreeNode(tempvalue);
    stackForDelete->push(ptemp);
    cout<<"ptemp->value:"<<ptemp->value<<endl;
    CreateBiTreePostIN(ptemp->leftChild,lchild_postsequence,lchild_midsequence);
    CreateBiTreePostIN(ptemp->rightChild,rchild_postsequence,rchild_midsequence);
}

void BinaryTree::MidSearchBiTree(TreeNode * ptemp)
{
    
    if(ptemp == NULL)
    {
        return;
    }
    MidSearchBiTree(ptemp->leftChild);
    cout<<ptemp->value;
    
    MidSearchBiTree(ptemp->rightChild);
}

int BinaryTree::TreeNode1Sum(TreeNode * ptemp)
{
    static int sum;
    if(ptemp == root)
    sum = 0;
    if(ptemp == NULL)
    {
        return sum;

    }
    TreeNode1Sum(ptemp->leftChild);
    if((ptemp->leftChild&&!ptemp->rightChild)||(ptemp->rightChild&&!ptemp->leftChild))
    {
        sum++;
    }
    TreeNode1Sum(ptemp->rightChild);
}

int BinaryTree::TreeNode0Sum(TreeNode * ptemp)
{
    static int sum;
    if(ptemp == root)
    {
        sum = 0;
    }
    if(ptemp == NULL)
    {
        return sum;
    }
    TreeNode0Sum(ptemp->leftChild);
    if(!ptemp->leftChild&&!ptemp->rightChild)
    {
        sum++;
    }
    TreeNode0Sum(ptemp->rightChild);

}
int BinaryTree::TreeNode2Sum(TreeNode * ptemp)
{
    static int sum;
    if(ptemp == root)
    {
        sum = 0;
    }
    if(ptemp == NULL)
    {
        return sum;
    }
    TreeNode2Sum(ptemp->leftChild);
    if(ptemp->leftChild&&ptemp->rightChild)
    {
        sum++;
    }
    TreeNode2Sum(ptemp->rightChild);
}
class Combination
{
     public:
    int height;
    int value;
   
    Combination(int height,int value)
    {
        this->height = height;
        this->value = value;
    }
};

list<Combination *>* BinaryTree::PostSearchBiTree()
{
    
    stack<TreeNode*> * stackforSearch = new stack<TreeNode*>;
    list<Combination *> * listforStore_Com = new list<Combination *>;
    TreeNode * ptemp = root;
    TreeNode * pre = root;
    stackforSearch->push(ptemp);
    while(!stackforSearch->empty())
    {
        
        while(stackforSearch->top())
        {
            ptemp = stackforSearch->top();
            stackforSearch->push(ptemp->leftChild);
            //cout<<"~~STACKFORSEARCH:"<<stackforSearch->size()<<endl;
        }
        
        stackforSearch->pop();
        if(stackforSearch->empty()) break;
        ptemp = stackforSearch->top();
        //cout<<"ptemp->value(POST):"<<ptemp->value<<endl;
        pre = ptemp;
        Combination* com = new Combination(stackforSearch->size(),ptemp->value);
        //cout<<"!!!size:"<<stackforSearch->size()<<endl;
        //cout<<"!!!value:"<<ptemp->value<<endl;
        listforStore_Com->push_back(com);
        //cout<<"!!!listforStore_Com:"<<listforStore_Com->size()<<"!!!"<<endl;
        stackforSearch->pop();
        if(stackforSearch->empty()) break;
        ptemp = stackforSearch->top();
        if(ptemp->rightChild != pre)
        stackforSearch->push(ptemp->rightChild);
        else stackforSearch->push(NULL);
        //getchar();
    }
    //cout<<"!!!listforStore_Com:"<<listforStore_Com->size()<<"!!!"<<endl;
    delete stackforSearch;
    return listforStore_Com;
}



int BinaryTree::GetTheHeight()
{
    list<Combination*> *listForStore = PostSearchBiTree();
    //cout<<"LISTSIEZE:"<<listForStore->size()<<endl;
    int MaxNum = 0;
    Combination * temp;
    list<Combination*>::iterator it;
    for(it = listForStore->begin();it!=listForStore->end();it++)
    {
        temp = *it;
        if(MaxNum<temp->height)
        MaxNum = temp->height;
    }
    delete listForStore;
    return MaxNum;

}

int BinaryTree::GetTheWidth()
{
    list<Combination*> *listForStore = PostSearchBiTree();
    
    list<Combination*> *listForWidth = new list<Combination*>;
    
   
    bool FLAG;
    for(list<Combination*>::iterator it = listForStore->begin();it!=listForStore->end();it++)
    {
        FLAG = false;
        
        for(list<Combination*>::iterator it_2 = listForWidth->begin();
        !listForWidth->empty()&&it_2!=listForWidth->end();it_2++)
        {
            if((*it_2)->height==(*it)->height)
            {
                (*it_2)->value++;
                FLAG = true;
                break;
            }

        }
        if(!FLAG)
        {
            Combination * com = new Combination((*it)->height,1);
            listForWidth->push_back(com);
        }
        



    }
    int MaxNum = 1;
    for(list<Combination*>::iterator it_2 = listForWidth->begin();it_2!=listForWidth->end();it_2++)
        {
            if(MaxNum<(*it_2)->value)
            {
                MaxNum = (*it_2)->value;
            }

        }
    delete listForStore;
    delete listForWidth;
    return MaxNum;

}

void BinaryTree::SwapTheBinaryTree(TreeNode * ptemp)
{
    if(ptemp==NULL)
    {
        return;
    }
    TreeNode * ptemp2;
    ptemp2 = ptemp->leftChild;
    ptemp->leftChild = ptemp->rightChild;
    ptemp->rightChild = ptemp2;
    SwapTheBinaryTree(ptemp->leftChild);
    SwapTheBinaryTree(ptemp->rightChild);
    
}

bool BinaryTree::JudgeComplete()
{
    list<Combination*> *listForStore = PostSearchBiTree();
    
    list<Combination*> *listForWidth = new list<Combination*>;
    // cout<<"Store::"<<listForStore->size()<<endl;
    bool FLAG;
    for(list<Combination*>::iterator it = listForStore->begin();it!=listForStore->end();it++)
    {
        FLAG = false;
        for(list<Combination*>::iterator it_2 = listForWidth->begin();it_2!=listForWidth->end();it_2++)
        {
            if((*it_2)->height==(*it)->height)
            {
                (*it_2)->value++;
                FLAG = true;
                break;
            }

        }
        if(!FLAG)
        {
             Combination * com = new Combination((*it)->height,1);
            if(!FLAG) listForWidth->push_back(com);

        }
       

    }
    //cout<<"width::"<<listForWidth->size()<<endl;
    
    int MaxNum = listForWidth->size();
    //cout<<"MAXNUM:"<<MaxNum<<endl;
    for(list<Combination*>::iterator it_2 = listForWidth->begin();it_2!=listForWidth->end();it_2++)
    {
        if((*it_2)->height<MaxNum&&(*it_2)->value!=pow(2,(*it_2)->height-1))
        {
             
             //cout<<(*it_2)->height<<"   "<<(*it_2)->value<<endl;
             
             cout<<"No!"<<endl;
             return false;
        }

    }
    cout<<"YES!"<<endl;
    delete listForStore;
    delete listForWidth;
    
    return true;
    
}